The present invention relates to optimization of circuit delays and more particularly, to circuit delay optimizing method and apparatus which determine optimum delay times of individual wiring lines by using a circuit arrangement and layout information available after layout of a circuit and wiring delay information such as wiring capacitances and fan-out numbers (indicative of the number of wiring lines branching from one wiring line) which are factors of determining wiring delay times estimated after the layout of a circuit.
Delay optimization is one of techniques for logic optimization and is employed to change a circuit configuration in such a manner that expected values of timings at signal paths in a circuit are satisfied. When performing delay optimization of a circuit whose layout has once been completed, layout information containing, for example, wiring capacitances obtained as a result of the layout is sent to a logic synthesizing unit and the logic synthesizing unit performs accurate delay calculation over the whole circuit for the sake of changing the circuit.
Prior to execution of actual circuit change, a layout unit carries out layout by using circuit connection information (layout information) and calculates wiring delays on the basis of the layout and decides whether the wiring delays are improved. In connection with a layout portion at which the delay time is improved, the calculated delay time is fed back to the logic synthesizing unit, so that an actual circuit change is executed by changing the logic.
In other words, the logic is changed for the purpose of improving the delay time but layout is not carried out after the logic change and therefore, the delay time after the logic change can be determined by estimation. Further, in order to decide whether the logic change succeeds in improvement of the delay time, more accurate presumption (estimation) of delay time is again required after the logic change.
A delay in a circuit can be determined by a sum of a delay owned by a gate per se called a gate delay and a delay in wiring called a wiring delay. The wiring delay is a function of a wiring capacitance and can be determined from the wiring capacitance through the medium of a predetermined function. Accordingly, the wiring capacitance will be handled as the wiring delay in the following description. When layout wiring proceeds, the gate delay remains unchanged but the wiring capacitance will change depending on the manner of layout wiring. In the case where layout is effected after a circuit change, the layout unit proceeds with the processing by using the placement and routing information of the original layout and accordingly, it sometimes happens that the original wiring capacitance almost remains unchanged at a portion where the wiring pattern has not been changed but the wiring capacitance changes greatly from the original value at a portion where the wiring topology has been changed.
Conventionally, with a view of coping with this problem, when delays are calculated using wiring capacitances after layout to perform suitable delay optimization, wiring capacitances are statistically processed with respect to the fan-out numbers of individual wiring lines of the existing layout to prepare information in advance, and the capacitance of a wiring line whose pattern is changed or of a newly established wiring line is determined from a fan-out number of the corresponding wiring line in the information.
This is because the wiring capacitance in layout is considered to be a function of the fan-out number and therefore, a wiring capacitance of a wiring line newly established after optimization is estimated from the statistical information of the individual wiring lines of the existing layout. This technique is described in pages 8-21-8-26 of "Design Compiler Family Reference Manual" published by Synopsys Company in the US in 1995.
A processing flow of this type of conventional technique will be described with reference to FIG. 4. Firstly, in step 400, the layout unit establishes wiring layout of an object circuit and calculates layout information containing wiring capacitances to provide layout information of individual wiring lines corresponding to individual wiring lines of the same circuit inputted to a logic synthesizing unit.
Next, in step 401, all wiring lines are sorted in accordance with the fan-out number and wiring capacitances supplied as layout information with respect to individual wiring lines are statistically processed to determine a wiring capacitance corresponding to a fan-out number.
In step 402, a candidate for a circuit change in logic synthesis is searched. If no candidate exists, the procedure ends. If a candidate exists, the program proceeds to step 403 so as to try a candidate circuit change.
In step 403, a wiring capacitance after the circuit change is estimated from the statistical information and a fan-out number after the circuit change, and a delay is calculated through the medium of a predetermined function. For a portion intact to the circuit change, layout information obtained from the layout unit is used without alteration.
In step 404, it is decided whether the delay after the circuit change is improved over that before the circuit change. If the delay is improved, the program proceeds to step 405 but if not improved, the circuit change is not adopted and another circuit change candidate is searched in step 402.
In step 405, the circuit change candidate is adopted and in step 406, data concerning the wiring capacitance of a portion which has been changed in wiring topology is updated. When a series of processes ends, the program returns to step 402 and a different circuit change candidate is searched.
The processing flow shown in FIG. 4 will be described more specifically by taking an instance where a circuit of FIG. 5 is changed by inserting a buffer 208 as shown in FIG. 6. In FIGS. 5 and 6, a circle corresponds to a gate of a circuit and an arrow connecting gates represents a wiring line, with the direction of the arrow indicating a direction of a signal flow.
In step 400, wiring capacitances associated with wiring lines 201 to 205 in FIG. 5 are calculated as 2 pF, 20 pF, 4 pF, 10 pF and 6 pF, respectively, to provide layout information. These wiring capacitances are assigned to corresponding wiring lines of the FIG. 5 circuit inputted to the logic synthesizing unit.
In step 401, the wiring capacitances are sorted with respect to the fan-out number. Namely, the wiring lines 201 and 203 having a fan-out number of 2 have wiring capacitances C1=2 pF and C3=4 pF and the wiring lines 202, 204 and 205 having a fan-out number of 3 have wiring capacitances C2=20 pF, C4=10 pF and C5=6 pF.
Next, these wiring capacitances are statistically processed to determine one wiring capacitance value with respect to the fan-out number. Here, they are averaged to indicate that a wiring capacitance value for one fan-out number is (2+4).div.2=3 pF in the case of the fan-out number being 2 and a wiring capacitance value for one fan-out number is (20+10+6).div.3=12 pF in the case of the fan-out number being 3.
It is now assumed that in the subsequent step 402, a circuit change candidate as shown in FIG. 6 is found and then a buffer of gate 208 as shown in FIG. 6 is inserted to the circuit of FIG. 5 and the wiring line 202 of FIG. 5 is divided into wiring lines 206 and 207.
Since the circuit change candidate exists, a wiring capacitance of a portion at which the circuit change is effected is estimated in step 403. The wiring line 206 has a fan-out number of 2 and therefore, the 3 pF wiring capacitance for the fan-out number being 2 is taken out of the statistical information and assigned to wiring capacitance C6 of the wiring line 6. Similarly, a wiring line 207 also having a fan-out number of 2 has wiring capacitance C7 to which 3 pF is assigned. By using these wiring capacitance values, wiring delays are estimated through the medium of the aforementioned predetermined function.
Next, in step 404, it is decided whether the delay of this circuit is improved. If improved, the circuit of FIG. 5 is changed to the circuit of FIG. 6 in step 405 and, in step 406, the wiring capacitance is updated to the value estimated in step 403. When a series of processes ends, the program returns to step 402 and another circuit change is tried.
In the wiring delay estimation in the conventional delay calculation, the wiring delay is calculated using a wiring capacitance determined in one-to-one correspondence to the fan-out number. This means that when wiring optimization is carried out and the wiring is changed, the same wiring capacitance is constantly determined for the same fan-out number.
Generally, as the length of wiring line increases, the wiring capacitance increases but in the conventional method, the distance between gates to be connected to each other is not taken into consideration. Accordingly, there is a possibility that the wiring capacitance of a wiring line which is originally long is underestimated.
Especially, with advanced miniaturization of circuits, the ratio of the wiring capacitance to the circuit total delay increases and a large error in the wiring capacitance prevents accurate delay calculation. A failure to perform accurate delay calculation raises a problem that effective delay optimization cannot be achieved.